//1.两数之和   https://leetcode.cn/problems/two-sum/description/
//给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

//你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
//你可以按任意顺序返回答案。
//示例 1：
//输入：nums = [2, 7, 11, 15], target = 9
//输出：[0, 1]
//解释：因为 nums[0] + nums[1] == 9 ，返回[0, 1] 。
//示例 2：
//输入：nums = [3, 2, 4], target = 6
//输出：[1, 2]
//示例 3：
//输入：nums = [3, 3], target = 6
//输出：[0, 1]
//提示：
//2 <= nums.length <= 104
//- 109 <= nums[i] <= 109
//- 109 <= target <= 109
//只会存在一个有效答案

//暴力解法 时间复杂度O（N^2）
// 固定一个数查找该数之前是否有值为 target- nums[i],找到直接返回
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        for (int i = 0; i < nums.size(); i++)
            for (int j = i - 1; j >= 0; j--)
            {
                if (j < 0) break;
                if (nums[j] + nums[i] == target) return { j,i };
            }
        return { -1,-1 };
    }
};

//借助hash 时间复杂度O（N）空间复杂度O（N）
// 固定一个数查找该数之前是否有值为 target- nums[i],找到直接返回
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++)
        {
            int value = target - nums[i];
            auto it = hash.find(value);
            if (it != hash.end())
                return { it->second,i };
            hash.insert({ nums[i],i });
        }
        return { -1,-1 };
    }
};



//2.判断两个字符串是否为字符重排
//https://leetcode.cn/problems/check-permutation-lcci/description/
//给定两个由小写字母组成的字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。
//示例 1：
//输入 : s1 = "abc", s2 = "bca"
//输出 : true
//示例 2：
//输入 : s1 = "abc", s2 = "bad"
//输出 : false
//说明：
//0 <= len(s1) <= 100
//0 <= len(s2) <= 100

class Solution {
public:
    bool CheckPermutation(string s1, string s2)
    {
        //判断两个字符串是否长度相等，不相等直接返回false
        if (s1.size() != s2.size()) return false;
        //统计其中一个字符串的每个字母出现的次数
        int hash[26] = { 0 };
        for (auto& ch : s1)
        {
            hash[ch - 'a']++;
        }
        //扫描另一个字符串看是否能重排
        for (auto& ch : s2)
        {
            //直接将第一个字符串的对应的字母次数减一
            hash[ch - 'a']--;
            //如果对应字母的次数减完后小于0，直接返回false
            if (hash[ch - 'a'] < 0) return false;
        }
        return true;
    }
};


//3.判断数组中是否存在任一重复元素|
//https://leetcode.cn/problems/contains-duplicate/description/
//给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
//示例 1：
//输入：nums = [1, 2, 3, 1]
//输出：true
//解释：
//元素 1 在下标 0 和 3 出现。
//示例 2：
//输入：nums = [1, 2, 3, 4]
//输出：false
//解释：
//所有元素都不同。
//示例 3：
//输入：nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
//输出：true

//解题思路和第一题类似
class Solution {
public:
    bool containsDuplicate(vector<int>& nums)
    {
        unordered_set<int> hash;
        for (int i = 0; i < nums.size(); i++)
        {
            int value = nums[i];
            if (hash.count(value))
            {
                return true;
            }
            hash.insert(value);
        }
        return false;
    }
};


//4.判断数组中是否存在任一重复元素||
//https://leetcode.cn/problems/contains-duplicate-ii/description/
//给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 
//且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
//示例 1：
//输入：nums = [1, 2, 3, 1], k = 3
//输出：true
//示例 2：
//输入：nums = [1, 0, 1, 1], k = 1
//输出：true
//示例 3：
//输入：nums = [1, 2, 3, 1, 2, 3], k = 2
//输出：false


//解题思路和第一题类似,加了需要判断在hash表中找到的重复元素的下标与当前元素的下标的差的绝对值小于等于k

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k)
    {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++)
        {
            int value = nums[i];
            auto it = hash.find(value);
            if (it != hash.end())
            {
                int index = it->second;
                if (abs(index - i) <= k)
                    return true;
            }
            //注意如果nums数组有重复元素需要对hash表的重复元素进行覆盖
            // 而insert对hash表已有元素不会进行覆盖
            // hash.insert({value,i});
            hash[value] = i;
        }
        return false;
    }
};



//5.字母异位次分组
//https://leetcode.cn/problems/group-anagrams/description/

//给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
//示例 1:
//输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
//输出 : [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]
//解释：
//在 strs 中没有字符串可以通过重新排列来形成 "bat"。
//字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
//字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。
//示例 2:
//输入: strs = [""]
//输出 : [[""]]
//示例 3 :
//    输入 : strs = ["a"]
//    输出 : [["a"]]
//
//解法：遍历strs把所有字母异位词分好组并插入到hash中, 再将分好的组返回
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs)
    {
        unordered_map<string, vector<string>> hash;
        //把所有字母异位词分好组并插入到hash中
        for (auto& s : strs)
        {
            string tmp = s;
            sort(tmp.begin(), tmp.end());
            hash[tmp].push_back(s);
        }
        //将分好的组返回
        vector<vector<string>>  ret;
        for (auto& [x, y] : hash)
        {
            ret.push_back(y);
        }
        return ret;
    }
};


